package algorithm.leetcode.medium;

/*
 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2021/1/20
 */
public class Question378 {

    public static void main(String[] args) {
        int[][] matrix = {{1,  5,  9}, {10, 11, 13}, {12, 13, 15}};
        int k = 8;
        Question378 question = new Question378();
        int smallest = question.kthSmallest(matrix, k);
        System.out.println(smallest);
    }

    /**
     * 思路：
     * 左上角元素是下限，右下角元素是上限，就有了一个值域，第 k 小的元素在这个值域中
     * 我们对值域进行二分查找，逼近值域中的目标值，第 k 小的元素
     * 算出中间值，并求出矩阵里小于等于这个中间值的有几个，count 个
     * count 和 k 比较，如果比 k 小，说明中间值小了，调整值域范围，
     * 否则，说明中间值大了，调整值域范围，一步步锁定目标值
     */
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        // 最小值
        int low = matrix[0][0];
        // 最大值
        int high = matrix[n - 1][n - 1];
        while (low <= high) {
            // 中间值
            int midVal = low + ((high - low) >> 1);
            // 矩阵中小于等于它的个数
            int count = countInMatrix(matrix, midVal);
            // 调整值域
            if (count < k) {
                low = midVal + 1;
            }else {
                high = midVal - 1;
            }
         }
        return low;
    }

    private int countInMatrix(int[][] matrix, int midVal) {
        int n = matrix.length;
        int count = 0;
        int row = 0;
        int col = n - 1;
        while (row < n && col >= 0) {
            if (midVal >= matrix[row][col]) {
                // 如果大于等于中间值  说明这列前面都小于中间值
                count += col + 1;
                // 下一行
                row++;
            }else {
                // 这一列前面一列
                col--;
            }
        }
        return count;
    }


}
